The present invention relates to a method of and apparatus for grouping failure paths of integrated circuit designs, and to a computer-readable medium for enabling a computer to perform such grouping.
Very large scale integrated (VLSI) circuit design is a complex and time consuming engineering task. Functional blocks are groupings of integrated circuits to be fabricated, e.g., adders, shifters, and clock distribution mechanisms. Before an integrated circuit can be fabricated, the integrated circuit must pass many correctness, i.e., verification, checks if the circuit has many functional blocks. One such verification check is a static timing analysis. A static timing analysis traces all signal paths through a circuit and verifies that all signal paths meet or exceed the required timing constraints, i.e., the circuit is able to operate at or above a specified frequency. Passing paths are signal paths meeting or exceeding the timing constraints and failing paths are signal paths not meeting the timing constraints.
FIG. 1 is a portion of an exemplary circuit design, generally indicated by reference numeral 100. Circuit design portion 100 includes a set of functional blocks, i.e., FB1, FB2, FB1A, FB2A, and FB3-FB16 referenced by numerals 102-119 respectively, connected via signal paths. Functional blocks 104, 110, and 116 represent functional blocks receiving a signal from another portion (not shown) of the circuit design or from an input port of the circuit design. Functional blocks 104, 110, and 116 derive a signal using signal paths to connected functional blocks 102 and 105, 108 and 111, 114 and 117, respectively.
Functional blocks 102-119 represent processing circuits, i.e., a set of one or more transistors, for processing the input signal received from other functional blocks of the circuit design (not shown) or from an input port (not shown) of the circuit design. Functional blocks 102-119 may be any of a wide range of processing functionality, e.g., a single transistor, an inverter, an arithmetic logic unit (ALU), a floating point unit (FPU), or any other logic processing unit. Functional blocks 102-119 process the received input signal and transmit a signal to either (1) another of the functional blocks 105-116 or (2) an output port (not shown) of the circuit design.
Typically in a timing analysis resulting from a computer simulation of a proposed circuit design, transistors comprising the integrated circuit are grouped into functional blocks, and a graph of connected functional blocks, e.g., the graph of portion 100 of FIG. 1, is constructed. Each functional block may contain one or more transistors or functional blocks.
The timing analysis converts the functional block graph (FIG. 1) to a path and node graph (FIG. 2) by converting the signal path connecting functional blocks into nodes and converting the functional blocks into connections between nodes. In other words, the nodes are extracted from the functional block graph signal paths and logically connected by paths based on the functional blocks. Thus, the signal path connecting FB1 to FB2 is converted to a node generally indicated by a dashed line object 120 in FIG. 1. The signal path connecting FB3 to FB1 and FB1A is converted to a node generally indicated by a dashed line object 121. Functional block 102 connecting node 120 and 121, i.e., FB1, is converted to the path connecting the nodes 120, 121. Using the above-described procedure, FIG. 2 is a path and node graph 200 of converted functional block graph portion 100 of FIG. 1. The timing analysis lists each path in path and node graph 200 as a series of nodes and delay times, i.e., the time required for processing to complete during a particular path traversal.
As a result of the timing analysis, each path is categorized as passing or failing based on slack (i.e., required time for the path to perform an allocated operation less the actual performance time) or frequency (i.e., what is the maximum frequency that can be used before the path fails to perform the operation). A single functional block frequently contains many thousands of paths. Users use a static timing tool to request a report of the first N paths. Typically the timing analysis indicates some subset of the requested N paths are failing paths.
FIG. 2 is an exemplary set of nodes and paths of the portion 100 of the circuit design of FIG. 1. Nodes A, B1, B2, C, D, E, F, G, H, and I represent the input functional block(s) to a functional block of a circuit design. B1 and B2 are duplicate nodes and one node (B1, or B2, as appropriate) should be investigated if the designer determines the other is failing. For instance, the functional blocks FB1, FB1A of FIG. 1 forming the path providing input to nodes B1, B2 of FIG. 2 may be copies of an ALU design functional block.
For illustrative purposes, it is assumed that nodes B1, B2, and F are failing nodes (dashed circles), i.e., paths containing these nodes fail to meet or exceed the timing constraints. As a result, the timing analysis for the node and path graph portion 200 of FIG. 2 results in a passing path list of the path made up of connected nodes D, E, and F, i.e., nodes 124, 125, and 123 respectively. Because paths are reported from the timing analysis as a connected series of the node names of nodes making up the path separated by periods, the passing path is referred to as xe2x80x98D.E.Fxe2x80x99. Using this identification scheme, the failing path list includes the following paths: A.B1.C, A.B2.C, D.B2.C, G.E.F, G.H.F, and G.H.I.F, respectively indicated by reference numerals 202-207 (shown as shaded paths).
Circuit designers receive timing analysis results identifying the nodes and paths of a circuit design, a corresponding timing delay for each path, and lists of passing and failing paths based on timing constraints for the circuit design. Because of the large number of paths in circuit designs, there are frequently large numbers of failing paths requiring correction to meet or exceed the timing constraints. Correcting each failing path in turn and re-running the timing analysis requires a large amount of time. Fortunately in many circuits, a single node can cause numerous path failures and if the particular node can be identified, the large amount of time and effort required to identify and correct several related path failures can be minimized. To this end, circuit designers use numerous approaches, e.g., rules of thumb, designer intuition, circuit topology knowledge, and engineering judgment, to minimize the amount of time and effort required to identify defective nodes and ultimately circuit designs.
One method used by circuit designers to reduce the number of failing paths is grouping related failing paths into sets. These groupings, i.e., sets of failing paths, are sometimes referred to as xe2x80x98bucketsxe2x80x99 by circuit designers and the process of grouping the failing paths is referred to as xe2x80x98bucketizingxe2x80x99. Because a node can occur in many paths, a single bad node delay, resulting, e.g., from a driver too small for output loading thereof, might cause many paths to fail. Fortunately, in many cases, a single fix to a particular functional block corresponding to the bad node can simultaneously fix all the remaining failing paths which include the node.
Another method used by circuit designers to reduce the number of failing paths under consideration for correction is common grouping of nodes corresponding to common functional blocks. Most often, common grouping is related to bus lines on integrated circuit designs. If a single line of a bus has a problem, e.g., a particular functional block for driving a signal on a particular line, often every line of the bus has the same problem because the particular functional block is frequently duplicated for all lines of the bus. With reference to FIG. 2, common grouping might be employed by a designer to group paths containing B1 and B2, i.e., FB1 with FB1A and FB2 with FB2A referring to FIG. 1, because the functional blocks are duplicates. Thus, grouping failing paths 202 and 203, respectively A.B1.C and A.B2.C, because the paths differ only based on duplicate nodes B1 and B2, reduces by one half the number of paths identified for correction.
Grouping paths into failing path sets using any of the above-identified methods and information helps make debugging and fixing a functional block more manageable. Different designers create different failing path sets. To create a collection of failing path sets, the designer starts with the timing analysis node and path result. A failing path from the timing analysis is used to create a first failing path set in the failing path set collection. The designer selects failing paths typically based on designer instinct or xe2x80x98gut feelxe2x80x99 and circuit knowledge. The selected failing path is added to the first failing path set. Using the above described methods, additional failing paths are selected from the timing analysis and added to the first failing path set. During the process of matching failing paths to failing path sets, if a failing path does not match an existing failing path set, then the user creates a new failing path set in the failing path set collection and assigns the failing path to the failing path set. After many sets have been created, the designer will group (assigning failing paths to the sets created so far) to see which failing paths remain, and then create new sets for those remaining failing paths. In the ideal case, the process continues until the user has sorted all failing paths into failing path sets; however, because of the very large number of failing paths in the typical circuit design, designers stop grouping failing paths before all paths have been considered.
There may be several thousand failing paths, e.g., 5,000 out of 100,000 paths of an integrated circuit design. Creating failing path sets and repeatedly grouping failing paths until all failing paths are in a set are tedious processes frequently requiring at least a day of a designer""s valuable time. While a designer is creating the sets, a team of engineers may be waiting for the results so they can start working on identifying and repairing the problems associated with the assigned sets.
Designers use their knowledge of the circuit design and rules of thumb to decide how to create a failing path set for a failing path. One rule of thumb is to identify a node with a very high routing delay. This approach works for some nodes in failing paths, but like any rule of thumb, there are counterexamples.
For example, because a global clock signal is distributed throughout the circuit, the corresponding timing path always has a high routing delay indicative of a failure path. However, the global clock signal appears in almost all passing paths as well, so the clock path is a poor choice to use for a failing path set.
Another problem encountered with previous approaches is a lack of sorting of failing paths, i.e., using previous approaches there is little or no failing path priority. Many of the failing path sets are created and filled using rules of thumb and the best guess of a designer. Additional information about the probability of failure of a given path is not taken into account to rank the failing paths. This information could be used to allocate limited design resources more efficiently.
As described above, there is a need in the art for an improved method of identifying failing path sets for failing path grouping.
The above described objects are fulfilled by a method of grouping failing paths of an analyzed integrated circuit. Failing paths, including series connected nodes having names, are in a list. Node pattern sets are represented as grouped node names. The node pattern in the node pattern set that is most likely to fail is determined in response to a measure of probability of failure of a node pattern in a path on the list. Paths most likely to fail based on the determined most likely to fail node pattern are placed in a failing path set. The determining and placing steps are repeated until each path on the list is in a failing path set by using paths not placed in a failing path set and node patterns not determined to be most likely to fail.
In an apparatus aspect, a preferred embodiment of the present invention includes a computer-readable medium having at least one sequence of machine executable instructions for grouping failure paths of an analyzed integrated circuit design in machine form. The execution of the instructions by one or more processors causes the one or more processors to determine the node pattern in the node pattern set that is most likely to fail in response to a measure of probability of failure of a node pattern in a path on the list. Paths most likely to fail based on the determined most likely to fail node pattern are placed in a failing path set. Further execution of the instructions by a processor causes the one or more processors to executed the sequence of instructions until each path on the list is in a failing path set by using paths not placed in a failing path set and node patterns not determined to be most likely to fail.
In a system aspect, a preferred embodiment of the present invention includes grouping failing paths of an analyzed integrated circuit design. The system includes a processor and a memory coupled to the processor. The memory stores failing paths and sequences of instructions for execution by the processor. The failing paths include series connected nodes having names and the failing paths are included in a list. The node names in the failing paths are represented as node patterns and grouped into node pattern sets. The sequences of instructions, when executed by the processor, cause the processor to determine the node pattern in the node pattern set that is most likely to fail in response to a measure of probability of failure of a node pattern in a path on the list. The paths determined most likely to fail based on the determined most likely to fail node pattern are placed in a failing path set. The instruction sequence, when executed by the processor, further causes the processor to execute the sequence of instructions until each path on the list is in a failing path set by using paths not placed in a failing path set and node patterns not determined to be most likely to fail.
Still other objects and advantages of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein the preferred embodiments of the invention are shown and described, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawings and description thereof are to be regarded as illustrative in nature, and not as restrictive.